class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        small = ListNode()
        small_head = small
        large = ListNode()
        large_head = large

        cur = head
        while cur != None:
            if cur.val < x:
                small.next = cur
                small = cur
            else:
                large.next = cur
                large = cur
            cur = cur.next
        #连接small和large节点
        small.next = large_head.next
        #断开large后续
        large.next = None
        return small_head.next
